package algorithms.leaning.class38;

import common.util.MyUtil;

/**
 * int[] d，d[i]：i号怪兽的能力
 * int[] p，p[i]：i号怪兽要求的钱
 * 开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
 * 如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上；
 * 如果你当前的能力，大于等于i号怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
 * <p>
 * 返回通过所有的怪兽，需要花的最少的钱数。
 *
 * @author guichang
 * @date 2021/7/18
 */

@SuppressWarnings("all")
public class code4_动态规划_贿赂怪兽 {

    public static void main(String[] args) {
        int[] d = MyUtil.createRandomArray(10, 1, 10);
        int[] p = MyUtil.createRandomArray(10, 1, 10);
        MyUtil.print(minMoney(d, p));
        MyUtil.print(minMoneyDp(d, p));
    }

    public static int minMoney(int[] d, int[] p) {
        if (d == null || p == null || d.length == 0 || d.length != p.length) {
            return 0;
        }
        return process(d, p, 0, 0);
    }

    /**
     * 当前来到了index位置，你的能力是power，通过所有怪兽花最少的钱数
     */
    private static int process(int[] d, int[] p, int index, int power) {
        // 来到最后了
        if (index == d.length) {
            return 0;
        }
        // 你的能力低，所以必须要贿赂
        if (power < d[index]) {
            return p[index] + process(d, p, index + 1, power + d[index]);
        }
        // 你的能力高，可贿赂可不贿赂，取最小值
        int p1 = process(d, p, index + 1, power);
        int p2 = p[index] + process(d, p, index + 1, power + d[index]);
        return Math.min(p1, p2);
    }

    public static int minMoneyDp(int[] d, int[] p) {
        if (d == null || p == null || d.length == 0 || d.length != p.length) {
            return 0;
        }
        int N = d.length;
        int SP = 0;
        for (int x : d) {
            SP += x;
        }
        int[][] dp = new int[N + 1][SP + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int power = SP; power >= 0; power--) {
                // 你的能力低，所以必须要贿赂
                if (power < d[index]) {
                    dp[index][power] = p[index] + getDp(dp, index + 1, power + d[index]);
                }
                // 你的能力高，可贿赂可不贿赂，取最小值
                else {
                    int p1 = getDp(dp, index + 1, power);
                    int p2 = p[index] + getDp(dp, index + 1, power + d[index]);
                    dp[index][power] = Math.min(p1, p2);
                }
            }
        }
        return dp[0][0];
    }

    private static int getDp(int[][] dp, int x, int y) {
        if (y >= dp[0].length) {
            return 0;
        }
        return dp[x][y];
    }

}